package Sort;

import org.junit.Before;
import org.junit.Test;

import java.util.Arrays;

public class MergeSort {

    int[] originNums = {0, 85, 96, 12, 77, 56, 63, 744, 354, 84,
            56, 13, 4567, 3, 165, 123, 46, 2, 156, 186, 4316, 465, 5};


    @Test
    public void mergeSort() {
        System.out.println(Arrays.toString(mergeSort(originNums, 0, originNums.length - 1)));
    }

    private int[] mergeSort(int[] nums, int l, int r) {
        if (l == r) {
            return new int[]{nums[l]};
        }
        int middle = (l + r - 1) / 2;
        int[] left = mergeSort(nums, l, middle);
        int[] right = mergeSort(nums, middle + 1, r);
        int[] newArray = new int[left.length + right.length];
        int li = 0;
        int ri = 0;
        int m = 0;
        while (li < left.length && ri < right.length) {
            if (left[li] <= right[ri]) {
                newArray[m++] = left[li];
                li++;
            } else {
                newArray[m++] = right[ri];
                ri++;
            }
        }
        while (li < left.length) {
            newArray[m++] = left[li];
            li++;
        }
        while (ri < right.length) {
            newArray[m++] = right[ri];
            ri++;
        }
        return newArray;
    }
}
